Background
Tree structures can be used to store data in an ordered fashion. For instance, one kind of tree structure is a balanced tree or “b-tree.” B-trees comprise a number of nodes organized along a parent-child relationship. In general, parent nodes will store data (or pointers and/or links to data) having a particular value and link to a number of “children” nodes that also store data (or, again, links to data) having a particular value. At leaf level, the nodes will store data. Typically, a given parent node will have a “left” child that stores values less than the smallest value stored by the parent and a number of “right” children, each corresponding to a subset of values in parent, that store data having values greater than the greatest value in that particular subset in the parent. Consider, for instance, a simple b-tree having three nodes. If the parent node stores data with a value of 2, then the left child node might store data with a value of 1 and the right child node might store data with a value of 3. When a tree has both its left arm and right arm populated (and any associated sub-arms) the tree is said to be “balanced.”
When accessing the various values stored in the nodes of a tree, it is necessary to jump across “levels” of the tree to retrieve the values. For instance, if you wanted to sequentially retrieve the values in the simple example above, you might begin with the left child to retrieve “1” and then jump to the parent level to retrieve “2” and jump back down, again, to the child level to retrieve “3”. In other words, traversing the tree sequentially can be non-linear in nature. In cases of larger trees in particular, this can require multiple visits to non-leaf levels, which results in additional costs in terms of IO (input and output), cache invalidation, and in worst case possible thrashing (repeated swap-in, swap-out) in memory-constrained environment.
In the drawings, like reference numbers generally indicate identical or similar elements. Additionally, generally, the left-most digit(s) of a reference number identifies the drawing in which the reference number first appears.